package com.java.comprehensive.arithmetic.leecode.easy;

import com.google.gson.Gson;
import org.springframework.beans.BeanUtils;
import util.ListNode;

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;

/**
 * @program: comprehensive-service
 * @description: 爬楼梯
 * @author: 窦绍飞
 * @create: 2021-11-25 10:28
 **/
public class LeetCode_70 {
	public static int climbStairs(int n) {
		if (n == 1)
			return 1;
		if (n == 2)
			return 2;

		int first = 1;
		int second = 2;
		for (int i = 3; i <= n; i++) {
			int third = first + second;
			first = second;
			second = third;
		}
		return second;
	}

	public static int fibonnacci(int n) {
		// 一次前进1 或者2 到达n 又两个方法，意思就是在n-1 或者n-2的时候 计算出n-1前面有多少个n-1 +n-2，n-2前面有多少个n-1 + n-2
		if (n == 0 || n == 1 || n == 2)
			return n;
		int[] mem = new int[n + 1];
		mem[1] = 1;
		mem[2] = 2;
		for (int i = 3; i <= n; i++) {
			mem[i] = mem[i - 1] + mem[i - 2];
		}
		return mem[n];
	}

	private static Map<Integer, Integer> map = new HashMap<>();

	public static int c_2(int n) {
		if (n == 1) {
			return 1;
		} else if (n == 2) {
			return 2;
		}
		if (map.get(n) != null) {
			return map.get(n);
		} else {
			int result = c_2(n - 1) + c_2(n - 2);
			map.put(n, result);
			return result;
		}
	}

	public static int c_3(int n) {
		if (n == 1) return 1;
		if (n == 2) return 2;
		int pre = 2;
		int prePre = 1;
		int result = 0;
		for (int i = 3; i <= n; i++) {
			result = pre + prePre;
			prePre = pre;
			pre = result;
		}
		return result;
	}

	public static void main(String[] args) throws ParseException {
		int n = 5;
		// 1 2 3 4 5
		int i = climbStairs(n);
		System.out.println(i);

		System.out.println("fibonnacci:" + fibonnacci(n));
	}
}
